package org.labuladong.动态规划算法.二维DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-20:45
 * @Description:
 * @version: 1.0
 */
public class LC_64_最小路径和 {

	class Solution {
		int[][] memo;
		public int minPathSum(int[][] grid) {
			int m = grid.length;
			int n = grid[0].length;
			// 构造备忘录，初始值全部设为 -1
			memo = new int[m][n];
			for (int[] row : memo)
				Arrays.fill(row, -1);
			return dp(grid, m - 1, n - 1);
		}
		int dp(int[][] grid, int i, int j) {
			// base case
			if (i == 0 && j == 0) {
				return grid[0][0];
			}
			if (i < 0 || j < 0) {
				return Integer.MAX_VALUE;
			}
			// 避免重复计算
			if (memo[i][j] != -1) {
				return memo[i][j];
			}
			// 将计算结果记⼊备忘录
			memo[i][j] = Math.min(
				dp(grid, i - 1, j),
				dp(grid, i, j - 1)
			) + grid[i][j];
			return memo[i][j];
		}
	}

	public static void main(String[] args) {

		int[][] grid = {
			{1,3,1},
			{1,5,1},
			{4,2,1}
		};

		System.out.println(new LC_64_最小路径和().new Solution().minPathSum(grid));
	}
}
